Table of Contents
This report is a preliminary version of the computational results included in the paper. Only instances generated with option spheredown are used since they seems to be hard instances.
In this section we report on the computational experiments conducted with the tri–objective branch–and–bound algorithm.
All instances are minimized, i.e. if an objective function \(z(x)\) is maximized, we minimize \(-z(x)\) instead. Note that in all instances only binary variables are considered.
The purpose of the computational study is to answer the following questions:
- What is the performance of the different algorithm configurations and which configurations perform the best ? In particular, is it worth doing objective branching ?
- Why does objective branching performs as it does ?
- How is the performance of the tri-objective B&B algorithm compared to objective space search algorithms?
Impelmentation details and algorithm configurations
All algorithms have been implemented in Julia \(1.0.1\). The experiments have been done on a computer with an Intel(R) Core(TM) i7-4785T CPU @ 2.20GHz processor and 16GB of RAM memory, using Linux Ubuntu 14.04 LTS.
In order to compute the linear relaxation at each node, the solver Bensolve is used (Lohne and Weibing, n.d.). To avoid parsing a lot a files at each node of the tree, we have implemented a wrapper that calls Bensolve, retrieve some outputs and insert them directly in our code as matrices. Numerical instabilities leading to missing non-dominated points in the final output have been detected while building the hyperplanes representation of the lower bound set. The matrix used when finding the normal to each hyperplane may in a few cases be close to singular (its determinant is close to zero). Hence a small value eps has been introduced so that if the determinant is less than or equal eps, then the hyperplane is discarded. For more information, we refer the reader to the section about numerical instabilities in Forget, Nielsen, and Gadegaard (2020). We have used eps \(= 0.001\) in all tests reported in this paper resulting in that no missing non-dominated points have been detected.
The variable selected in Step 5 of the algorithm differs depending on whether objective branching is applied or not. If no objective branching is performed, the algorithm will branch on the free variable that is the most often fractional among the extreme points of the lower bound set, given that at least one of the variables has a fractional value. If no variable has a fractional value in any of the extreme points, the variable that is the most often different (i.e. with the average value closest to \(0.5\)) is chosen. If objective branching is enabled, the rule is the same, except that a different variable may be chosen in each sub-problem. Indeed, given a sub-problem \(P(\eta,s)\) in the objective space, only the extreme points of the lower bound set included in \(P(\eta,s)\) (i.e. that dominates \(s\)) will be considered. In case there are multiple possible choices or no extreme point included in \(P(\eta,s)\), the variable with the smallest index will be chosen.
To test different algorithm configurations we use the following parameters:
nSdenotes the node selection method (Step 1 of Algorithm 1). Two values are possible:B: breadth first strategy.D: depth first strategy.
oBdenotes the objective branching strategy. Three configurations are tested:N: no objective branching is performed. This is the equivalent of skipping Step 4 of Algorithm 1.E: objective branching is applied as described in Algorithm 2.C: objective branching is applied as described in Section 4.3.
This leads to 6 configurations: B|N, B|E, B|C, D|N, D|E and D|C. We refer the reader to Forget, Nielsen, and Gadegaard (2020) where more configurations such as different variable selection rules (Step 5 of the algorithm).
Test instances
| \(n\) | # | |
|---|---|---|
| AP | 36, 49, 64, 121 | 10.0 |
| KP | 10, 15, 20, 25, 30, 35, 40 | 29.9 |
| UFLP | 30, 42, 56, 72 | 10.0 |
A total of 289 instances (see Table 1) has been generated. Three problem classes are considered: the linear assignment problem (AP), the knapsack problem (KP) and the uncapacitated facility location problem (UFLP). The mathematical programming formulation for each problem is given in the appendix. The number of variables in each problem class have been increased until no algorithm configurations could find an exact solution within a time limit of half an hour (1800 seconds).
The objective coefficients are generated in the range [1, 1000] on the lower part of a 3D sphere using the R package Relund Nielsen (2020). Hence a high number of the coefficient vectors for the variables are non-dominated among each other (91% for AP and 96% for KP). This way of generating the objective coefficients has been tested against other methods and seems to result in solutions with a high number of non-dominated points (Forget, Nielsen, and Gadegaard 2020) (implying hard instances). For UFLP instances the same generation method has been used. However, since two cost groups exists (see the appendix), a range of [1, 1000] has been used for generating the cost of assigning a customer to a service and a range of [1, 100] for generating the cost for opening a service. All objective coefficients are all integer.
For the AP the constraints are fixed given the problem size. The same holds for the UFLP when assuming the number of facilities equals the number of customers. For KP instances, the integer coefficients of the constraint are generated randomly in the range [1,15]. The right-hand side is set equal to half of the sum of the coefficients on the right hand side [LRN: Rounded???].
Output statistics
The following statistics will be considered:
cpu: total CPU time expressed in seconds used to solve an instance with a given configuration|YN|: size of \(\mathcal{Y}_N\), i.e. number of non-dominated points which can be partitioned intose: number of supported extreme points,sne: number of supported non-extreme points,us: number of unsupported points.
node: number of nodes explored in the branching tree to solve an instance with a given configurationprune: how leaf nodes are pruned partitioned intoI: number of leaf nodes pruned by infeasibility,O: number of leaf nodes pruned by optimality,D: number of leaf nodes pruned by dominance.
Comparison of the performance of the different configurations
[LRN: put a star for n if some instances are unsolved for all configurations. For ex KP 35 -> 21 config with at least 1 config solved -> put 30* instead]
In this section, performance profiles will be used to answer the question. It shows how many instances has been solved at any point in time for a given configuration. The greater this number is, the better the configuration is. Note that if the cpu time exceed 1800 seconds (30 minuts) for a configuration, the instance is considered as unsolved for this configuration.
[LRN: add all the instances for these performance profiles (consider the “exact” configurations as unsolved for larger instances, given the fact that there are many unsolved for even smaller instances, even thought we don’t have the statistic for it ?)]
Figure 1: Performance plots for the different problem classes
In Figure ??, only Assignment problems up to 64 variables, Knapsack problems up to 30 variables and Uncapacitated Facility Location problems up to 42 variables are considered.
The first observation is that B|E and D|E seem to perform the worst, especially for AP and UFLP. Although for KP, this observation is less obvious, these configurations are still among the worst ones. Both for KP and UFLP, the best objective branching configuration is the C, while it performs better to don’t have any objective branching prodecure for AP. These observations will be explored with more details in the next section.
[LRN: Plot for winning configurations -> n as x-axis and percentages of instances as y-axis. Have a color for the 6 configurations + another one for unsolved instances for all the configurations. Do a “stack plot”, in the spirit of the plot called “Pct for each configuration given 10 bins” in Research question 3 from the old report] [extra observation: with such a plot, we will be able to see that the number of unsolved instances grows with the size of the instance as well]
[NF: a few words about winning configurations]
Another observation is that in general, breadth first strategies tend to perform better than depth first strategies in this branch and bound framework. A possible explanation is that the linear relaxation of the problems studied is of good quality in the single-objective case [ref ?]. Thus, integer extreme points can be found very early (i.e. at a very low depth) in the branch and bound tree. For example, all the extreme points of the linear relaxation of an AP are integer and are thus new candidates for being part of the final non-dominated set. Hence, while using depth first strategies, the branch and bound algorithm tends to focus to specific parts of the objective space one by one; using breadth first strategies offer a better coverage of all the objective space earlier and thus, yields better upper bound sets earlier.
[Make curved lines for this plot, so that it becomes easier to read (in case we want to keep it)]
Figure 2: Reverse performance plots for the different problem classes
Reverse performance plot for the different algorithm configurations are given in Figure 2.
Why does objective branching performs as it does ?
[LRN: prune column as stack plot. One color for infeasibility, optimality and dominance. n as x-axis, percentages as y-axis.]
[LRN: number of nodes as a plot. One line for each configuration, n as x-axis, number of nodes as y-axis.]
[LRN: average depth as a plot. One line for each configuration, n as x-axis, average depth as y-axis. You may drop the N configurations for OB here, as they are not used.]
| n | # | YN (se, sne, us) | cpu | win | nodes (d leaf) | prune (I/O/D) | cpu | win | nodes (d leaf) | prune (I/O/D) | cpu | win | nodes (d leaf) | prune (I/O/D) | cpu | win | nodes (d leaf) | prune (I/O/D) | cpu | win | nodes (d leaf) | prune (I/O/D) | cpu | win | nodes (d leaf) | prune (I/O/D) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| AP | ||||||||||||||||||||||||||
| 36 | 10 | 160 (14/0/86) | 7.8 [3.5,11.2] | 0 | 2594 [3,17,26] | [91,5,4] | 2.8 [1.9,3.5] | 0 | 1540 [3,18,27] | [83,11,6] | 3 [2.1,3.7] | 0 | 1783 [3,19,27] | [83,12,5] | 1.4 [1.1,1.7] | 5 | 807 [6,11,16] | [0,74,26] | 8.4 [3.5,14.7] | 0 | 2640 [3,18,27] | [91,7,2] | 1.4 [1.1,1.6] | 5 | 831 [6,11,16] | [0,76,24] |
| 49 | 10 | 348 (8/0/92) | 101.2 [35.9,246.8] | 0 | 11225 [3,21,37] | [92,3,5] | 14.9 [11.4,21.4] | 0 | 4933 [3,25,38] | [82,8,11] | 16.1 [12.3,23.4] | 0 | 6170 [3,26,38] | [83,9,8] | 7.8 [6,10] | 3 | 2573 [7,13,20] | [0,59,41] | 152.7 [58.1,302.7] | 0 | 12037 [3,22,38] | [94,3,2] | 7.6 [6,9.8] | 7 | 2847 [7,13,21] | [0,62,38] |
| 64 | 10 | 741 (5/0/95) | 1171.6* [498,1800] | 0 | 43664 [3,26,51] | [92,1,7] | 67.2 [47.5,92.5] | 0 | 13811 [3,30,52] | [79,6,15] | 82.3 [66.8,114] | 0 | 20584 [3,33,53] | [82,7,11] | 34.5 [24.8,44.8] | 5 | 7414 [8,15,26] | [0,47,53] | 1550.8* [878.6,1800] | 0 | 47007 [3,27,52] | [95,2,3] | 34 [23.4,43.5] | 5 | 8558 [8,15,27] | [0,51,49] |
| 121 | 10 | 3982 (2/0/98) | NA | NA | NA | 1758.2* [1548.5,1800] | 2 | 115543 [3,44,83] | [70,2,28] | 1800* [1800,1800] | 0 | 265197 [3,56,105] | [78,4,18] | 1527.5* [1085.8,1800] | 3 | 73985 [10,19,41] | [0,27,73] | NA | NA | NA | 1520* [1051,1800] | 5 | 109189 [10,20,44] | [0,32,68] | ||
| 40 | 1308 (3/0/97) | NA | NA | NA | 460.8* [1.9,1800] | 2 | 33957 [3,29,50] | [78,7,15] | 475.3* [2.1,1800] | 0 | 73434 [3,33,56] | [82,8,10] | 392.8* [1.1,1800] | 16 | 21195 [8,14,26] | [0,52,48] | NA | NA | NA | 390.7* [1.1,1800] | 22 | 30356 [8,15,27] | [0,55,45] | |||
| 30 | 1308 (3/0/97) | 426.9* [3.5,1800] | 0 | 19161 [3,21,38] | [92,3,5] | NA | NA | NA | NA | NA | NA | NA | NA | NA | 570.6* [3.5,1800] | 0 | 20561 [3,22,39] | [94,4,2] | NA | NA | NA | |||||
| KP | ||||||||||||||||||||||||||
| 10 | 30 | 43 (28/0/72) | 0.2 [0.1,0.4] | 0 | 350 [5,9,11] | [71,22,6] | 0.2 [0.1,0.3] | 25 | 315 [5,9,11] | [63,28,8] | 0.2 [0.1,0.4] | 0 | 371 [5,9,11] | [64,32,4] | 0.2 [0.1,0.3] | 5 | 336 [5,9,11] | [28,46,26] | 0.3 [0.1,0.7] | 0 | 404 [5,9,11] | [71,26,3] | 0.2 [0.1,0.3] | 0 | 393 [5,9,11] | [33,49,18] |
| 15 | 30 | 145 (16/0/84) | 3.7 [1.3,9.2] | 0 | 2951 [6,11,16] | [79,12,10] | 2.4 [0.9,5.5] | 22 | 2238 [7,12,16] | [67,19,14] | 3.2 [1.5,7.1] | 1 | 3117 [7,13,16] | [70,21,9] | 2.9 [1.3,5] | 5 | 2499 [7,13,16] | [12,43,45] | 6.7 [2,19] | 0 | 3910 [6,12,16] | [81,14,5] | 3.4 [1.9,5.7] | 2 | 3540 [7,13,16] | [19,46,35] |
| 20 | 30 | 329 (10/0/90) | 35.6 [3.3,147.2] | 0 | 16899 [6,14,21] | [84,6,11] | 18.2 [2.5,43.8] | 30 | 10335 [7,16,21] | [72,12,16] | 28.5 [3.2,71.8] | 0 | 18618 [7,16,21] | [75,14,11] | 26.4 [5,50.6] | 0 | 12484 [7,16,21] | [9,43,49] | 103.5 [4.4,413.6] | 0 | 27738 [6,15,21] | [88,7,5] | 39.3 [6.7,83.6] | 0 | 23616 [7,17,21] | [14,43,43] |
| 25 | 30 | 564 (8/0/92) | 117.1 [38.1,288.4] | 0 | 40906 [6,16,26] | [84,4,12] | 60.8 [23.5,137.7] | 29 | 22963 [7,18,26] | [70,9,20] | 104.4 [41.6,267.2] | 1 | 53473 [8,19,26] | [75,10,15] | 104.7 [46.4,184.8] | 0 | 28759 [7,19,26] | [3,41,56] | 414* [89,1800] | 0 | 85434 [6,17,26] | [90,5,6] | 189.8 [82.2,410.4] | 0 | 71319 [7,20,26] | [6,44,50] |
| 30 | 30 | 1049 (6/0/94) | 820.6* [127.2,1800] | 0 | 126692 [6,18,30] | [85,2,13] | 307.8 [101.6,650.6] | 30 | 64778 [8,21,31] | [70,7,23] | 508.6 [147,1130.2] | 0 | 179463 [8,22,31] | [75,8,16] | 523.2 [196.3,1018.1] | 0 | 82540 [8,22,31] | [2,43,55] | 1498.9* [185.9,1800] | 0 | 184964 [6,20,31] | [91,3,6] | 1065.9* [323.1,1800] | 0 | 241410 [7,24,31] | [4,47,49] |
| 35 | 30 | 1832 (3/0/97) | 1800* [1800,1800] | 0 | 57683 [6,13,15] | [74,0,26] | 1295.5* [633.9,1800] | 29 | 131861 [8,22,32] | [65,5,30] | NA | NA | NA | 1722.9* [1317.3,1800] | 0 | 112353 [8,22,28] | [1,24,76] | 1800* [1800,1800] | 0 | 200125 [7,23,36] | [92,2,6] | 1800* [1800,1800] | 0 | 241050 [9,27,36] | [3,36,60] | |
| 35 | 29 | 1832 (3/0/97) | NA | NA | NA | NA | NA | NA | 1670.8* [785.1,1800] | 1 | 367515 [8,25,36] | [75,6,19] | NA | NA | NA | NA | NA | NA | NA | NA | NA | |||||
| 40 | 29 | 1980 (0/0/100) | NA | NA | NA | 1799.8* [1792.8,1800] | 29 | 87052 [8,18,21] | [44,1,55] | 1800* [1800,1800] | 0 | 432478 [10,28,41] | [75,4,20] | 1800* [1800,1800] | 0 | 55725 [8,17,20] | [0,3,97] | NA | NA | NA | 1800* [1800,1800] | 0 | 202482 [11,31,41] | [2,32,66] | ||
| 209 | 844 (4/0/96) | NA | NA | NA | 491.6* [0.1,1800] | 194 | 45451 [7,16,23] | [65,12,24] | NA | NA | NA | 591.4* [0.1,1800] | 10 | 42034 [7,17,22] | [8,35,57] | NA | NA | NA | 694.5* [0.1,1800] | 2 | 111540 [8,20,26] | [12,42,46] | ||||
| 180 | 844 (4/0/96) | 462.9* [0.1,1800] | 0 | 40914 [6,13,20] | [80,8,13] | NA | NA | NA | NA | NA | NA | NA | NA | NA | 637.2* [0.1,1800] | 0 | 83763 [6,16,24] | [86,10,5] | NA | NA | NA | |||||
| 208 | 844 (4/0/96) | NA | NA | NA | NA | NA | NA | 576.9* [0.1,1800] | 3 | 148322 [8,19,26] | [73,14,14] | NA | NA | NA | NA | NA | NA | NA | NA | NA | ||||||
| UFLP | ||||||||||||||||||||||||||
| 30 | 10 | 325 (14/0/86) | 33.4 [18.3,64.1] | 0 | 6158 [3,17,26] | [89,6,5] | 8.4 [6.2,12.4] | 3 | 3157 [3,19,26] | [75,16,9] | 8.9 [6.1,12.3] | 3 | 3868 [3,20,26] | [75,18,7] | 9.4 [5.9,14.5] | 3 | 3517 [7,14,21] | [0,65,35] | 47.2 [25.3,108] | 0 | 6758 [3,17,26] | [90,8,3] | 9.4 [6.8,15.3] | 1 | 4270 [7,14,22] | [0,70,30] |
| 42 | 10 | 996 (8/0/92) | 1207.7* [293.1,1800] | 0 | 43101 [4,22,38] | [91,3,6] | 71.8 [50.7,94.2] | 6 | 14976 [4,25,39] | [76,10,14] | 77.5 [48.9,110.9] | 4 | 20581 [4,26,39] | [77,13,10] | 94.7 [72.1,113.8] | 0 | 17321 [7,17,31] | [0,51,49] | 1595.5* [580.4,1800] | 0 | 47026 [4,22,39] | [93,4,3] | 119 [80.3,146.3] | 0 | 27599 [7,18,32] | [0,57,43] |
| 56 | 10 | 2257 (6/0/94) | NA | NA | NA | 423 [250.1,610.6] | 9 | 47652 [5,30,53] | [75,7,17] | 503.1 [260,835.2] | 1 | 82880 [5,32,53] | [78,9,13] | 688.5 [437.2,1011.5] | 0 | 55407 [7,20,39] | [0,40,60] | NA | NA | NA | 972.9 [514.6,1552.7] | 0 | 108010 [7,21,41] | [0,47,53] | ||
| 56 | 1 | 2257 (6/0/94) | 1800* [1800,1800] | 0 | 26956 [4,14,18] | [89,0,10] | NA | NA | NA | NA | NA | NA | NA | NA | NA | 1800* [1800,1800] | 0 | 83684 [5,27,53] | [94,3,3] | NA | NA | NA | ||||
| 72 | 10 | 4079 (3/0/97) | NA | NA | NA | 1624.4* [1260.4,1800] | 10 | 102228 [5,32,62] | [73,5,22] | 1763.8* [1518.2,1800] | 0 | 219087 [5,36,70] | [77,7,16] | 1800* [1800,1800] | 0 | 48682 [7,17,20] | [0,18,82] | NA | NA | NA | 1800* [1800,1800] | 0 | 129569 [9,24,48] | [0,45,55] | ||
| 40 | 1914 (5/0/95) | NA | NA | NA | 531.9* [6.2,1800] | 28 | 42003 [4,27,45] | [75,10,15] | 588.3* [6.1,1800] | 8 | 81604 [4,28,47] | [77,12,11] | 648.1* [5.9,1800] | 3 | 31232 [7,17,28] | [0,44,56] | NA | NA | NA | 725.3* [6.8,1800] | 1 | 67362 [7,19,36] | [0,55,45] | |||
| 21 | 1914 (5/0/95) | 676.7* [18.3,1800] | 0 | 24740 [4,19,32] | [90,4,6] | NA | NA | NA | NA | NA | NA | NA | NA | NA | 868* [25.3,1800] | 0 | 29596 [4,20,34] | [92,6,3] | NA | NA | NA | |||||
As shown previously, using the E configurations are not the most efficient configurations for the branch and bound algorithm. As explained in Section [4.3], as it may create several sub-problems in the objective space, it may create more nodes in the branch and bound tree, which may lead to higher computational times if the algorithm cannot explore them all fast enough. In practice, as it can be seen in Table 2, in general, E configurations indeed produce more nodes in the tree than the other configurations. Furthermore, it seems that these nodes are also explored slower than in other versions. For example, Table 2 shows that for Knapsack problems for n = 30, the number of nodes for the configurations D|C and D|E is approximatively the same (between 180000 and 190000). However, the first configuration is about 3 times faster than the second one.
As most of the computational time is spent in computing the lower bound set in this branch and bound framework (see [report]), the last observation may indicates that the sub-problems generated in the E configurations tends to be harder. This observation makes sense, as the purpose of objective branching as described in Algorithm 2 is to produce more sub-problems (and thus get wider trees), hoping that the tree will go less deep by making more local decision. When we look at the average depth of the tree in 2, it can be seen that it is generally lower for E than for C. Thus, it means that the nodes in E configurations are closer to the root node and thus, the corresponding sub-problems may be more complex. Indeed, the more a node is deep in the tree, the less complex the lower bound set tends to be (up to a single point at depth \(n + 1\)). This phenomenon may be minimized by introducing for example an updating procedure of the lower bound set, instead of a computation from scratch at each node as it is done currently in our implementation. Hence, the complexity of computing the lower bound set, no matter how deep it is in the tree, would be approximatively the same.
Another way to improve and possibly make E competitive would be to make more use of the local information provided by the sub-problems in the objective space. For example, as presented in [I have to find ref again, it’s somewhere in my references list], pre-processing in the multi-objective case has much less impact than in the single-objective case, as the efficient solutions may differ a lot. However, one could imagine that the solutions are more likely to be close in a specific part of the objective space and thus, by localising the branch and bound, pre-processing or introducing cuts may have a significantly more impact.
Except for AP, the C configurations are performing better than the N configurations. A first explanation of the efficiency of C for KP and UFLP is that for a given node \(\eta\), the C configurations will focus on a specific part of the objective space (a cone defined by \(d^N(\eta)\)). Thus, the lower bound sets tends to be less complex (some areas of the objective space are discarded before computation, while it is fully considered in the N version), which means possibly spending less time in the most expensive part of the branch and bound (computing the lower bound sets).
In addition to that, the way nodes are fathomed is highly influenced. Indeed, as it can be seen in Table 2, in the C configurations, the proportion of nodes fathomed by infeasibility tends to be much higher than for the N configurations. Besides, fathoming a node by infeasibility is faster than fathoming a node by optimality or by dominance. Indeed, to fathom by dominance or optimality, having the lower bound set computed is required. On the contrary, testing the feasibility of the sub-problem is the first thing done when a node is being explored and thus, a node fathomed by infeasibility is explored faster (see [report] for how much faster it is in practice).
The case of AP is a special. Indeed, in the N version, as the single-objective AP is in P, all the extreme points of the lower bound sets will always be integer. Thus, when a variable is chosen for branching, the special branching rule is triggered: the one chosen is the variable that is the most often different. However, in the C configurations, due to the fact that new constraints are added, the extreme points may have fractional values and thus, the branching rule differs from N configurations. It seems to have a significant impact on the branch and bound tree, which make the N configurations be the best.
In conclusion, it seems that how objective branching behave and whether it is efficient or not is very sensitive to the choices made in the other components of the branch and bound tree (variable selection, lower bound set, pre-processing…). The reader is refered to [report] to see more about that.
How is the performance of the tri-objective B&B algorithm compared to objective space search algorithms?
The best configuration of our branch and bound framework will now be compared to an efficient objective space search algorithm from the litterature [ref PhD Tamby]. Note that the goal of this paper is more like reaching a new step in making the branch and bound efficient in the multi-objective case by extending a concept that made branch and bounds more efficient in the bi-objective case, than to design an algorithm that performs better than objective space search algorithms on a specific set of instances. However, as the goal for futur research is to obtain a competitive branch and bound algorithm in the multi-objective case, we still want to compare to an objective space search algorithm, to see how far this goal is.
The principle of the algorithm from [ref Tamby] is to explore sub-problems that are defined by the current set of local upper bounds, that itself evolve when new non-dominated points are found. Using this approach, the authors expose a way to warmstart the MIP solver for each sub-problem expored as well as rules that discard sub-problems without even solving them, which both greatly improve the computational time. They show in their experiments that their algorithm performs better than some of the classical objective space search algorithm from the litterature.
As the LP solver in Bensolve is GLPK, the MIP solver that we will use for this algorithm is GLPK as well. Due to a technical constraint in the chosen programming language (Julia), the MIP solver could not be warmstarted. Hence, one should keep in mind that the cpu times for the objective space search algorithm are upper bounds on their actual cpu time.
[LRN: performance profile -> best config B&B vs Objective Space Search (OSS) algorithm. See stat_OSS.csv, columns “solved” (1 if instance solved, 0 otherwise) and “cpu” (cpu time expressed in seconds) for OSS algorithm. One performance profile per problem class ?]
[NF: a few words about the results]
–>
–>
–> –> –> –> –> –> –> –> –> –> –> –> –> –>
–>
–> –> –> –> –> –> –> –> –> –> –> –> –> –>
Detailed results for each instance
Detailed results for each instance can be generated using instance.Rmd. The report is already generated for some of the instances (see links in the table with input statistics). Some instances that might be of interest:
- Instances with lowest number of nondominated points: Forget20-KP_10_3_1-1000_spheredown_1_10, Forget20-KP_10_3_1-1000_spheredown_2_10, Forget20-KP_10_3_1-1000_spheredown_2_2
- Instances with highest number of nondominated points (solved): Forget20-AP_11_3_1-1000_spheredown_1_1, Forget20-AP_11_3_1-1000_spheredown_1_4, Forget20-UFLP_8_3_1-1000_1-100_spheredown_1_6
- Instances with lowest unsupported nondominated points percentage: Forget20-KP_10_3_1-1000_spheredown_2_10, Forget20-KP_10_3_1-1000_spheredown_2_2, Forget20-KP_10_3_1-1000_spheredown_2_8
- Instances with highest unsupported nondominated points percentage: Forget20-AP_11_3_1-1000_spheredown_1_1, Forget20-AP_11_3_1-1000_spheredown_1_3, Forget20-AP_11_3_1-1000_spheredown_1_4
- Instances with highest supported non-extreme nondominated points percentage: Forget20-AP_11_3_1-1000_spheredown_1_1, Forget20-AP_11_3_1-1000_spheredown_1_10, Forget20-AP_11_3_1-1000_spheredown_1_2
- Instances with highest variance in cpu time: Forget20-AP_8_3_1-1000_spheredown_1_2, Forget20-AP_8_3_1-1000_spheredown_1_3, Forget20-UFLP_6_3_1-1000_1-100_spheredown_1_8
Forget, N., L. R. Nielsen, and S. L Gadegaard. 2020. “Computational Results (All Instances).” Aarhus University. https://mcdmsociety.github.io/MOrepo-Forget20/report.html.
Lohne, A., and B. Weibing. n.d. “Bensolve.” http://www.bensolve.org/.
Relund Nielsen, Lars. 2020. GMOIP: Tools for 2D and 3D Plots of Single and Multi-Objective Linear/Integer Programming Models. https://github.com/relund/gMOIP/.